/**
 * @author ChaP
 * @date 2019/05/23
 * @describe:
 */
package CodingTest.AC20190522;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**leetcode - 451
 * 给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

 示例 1:

 输入:
 "tree"

 输出:
 "eert"

 解释:
 'e'出现两次，'r'和't'都只出现一次。
 因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
 示例 2:

 输入:
 "cccaaa"

 输出:
 "cccaaa"

 解释:
 'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
 注意"cacaca"是不正确的，因为相同的字母必须放在一起。
 示例 3:

 输入:
 "Aabb"

 输出:
 "bbAa"

 解释:
 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
 注意'A'和'a'被认为是两种不同的字符。
 */
public class frequencySort {
    //方法一：利用两个数组分别记录出现的频率和字符的顺序
    //A：65 a:97
    public String frequencySort(String s){
        int[] a = new int[256];
        HashMap<Character,Integer> hs = new HashMap<Character, Integer>();
        for(int i =0;i<s.length();i++){
            a[s.charAt(i) ] ++;
        }
        StringBuffer sb = new StringBuffer();
        int[] b = a.clone();
        Arrays.sort(a);
        for(int j = 255;j>=0&&a[j]>0;j--){
            for(int k = 0;k<256;k++){
                if(a[j] == b[k]){
                    while(b[k]-- >0) {
                        sb.append((char) k);

                    }
                }
            }
        }
        return sb.toString();
    }


    public static void main(String[] args) {
        String s1 = "tree";
        frequencySort fs = new frequencySort();
        System.out.println(fs.frequencySort(s1));
    }
}
